#include<iostream>
#include<vector>
using namespace std;
int partition(vector<int>& nums,int l,int r);
void quickSort(vector<int>& nums,int l,int r);
void printNums(vector<int>& nums);
int main(){
    vector<int> nums={1,2,5,4,1,6};
    quickSort(nums,0,nums.size()-1);
    printNums(nums);
    return 0;
}
int partition(vector<int>& nums,int l,int r){
    int i=l,j=r;// 以 nums[l] 作为基准数
    while(i<j){
        while(i<j && nums[j]>=nums[l]) j--;
        while(i<j && nums[i]<=nums[l]) i++;
        swap(nums[i],nums[j]);
    }
    swap(nums[i], nums[l]);//因为最后找到的是num[l]小的元素，所以当i>=j的时候，num[i]的值不管被没被交换一定是 最后一个比num[l]小的元素，num[l]的左边都比num[l]小,右边都比num[l]大
    return i;
}
void quickSort(vector<int>& nums,int l, int r){
    // 子数组长度为 1 时终止递归
    if (l >= r) return;
    // 哨兵划分操作
    int i = partition(nums, l, r);
    // 递归左（右）子数组执行哨兵划分
    quickSort(nums,l,i-1);
    quickSort(nums,i+1,r);
}
void printNums(vector<int>& nums){
    for(vector<int>::iterator it=nums.begin();it!=nums.end();++it){
        cout<<*it<<" ";
    }
}